Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Solution:

  1. public class Solution {
  2.   public int maximumGap(int[] nums) {
  3.       if (nums == null || nums.length < 2) {
  4.         return 0;
  5.       }
  7.       int n = nums.length;
  9.       // m is the maximal number in nums
  10.       int m = nums[0];
  11.       for (int i = 1; i < n; i++) {
  12.         m = Math.max(m, nums[i]);
  13.       }
  15.       int exp = 1; // 1, 10, 100, 1000 ...
  16.       int R = 10; // 10 digits
  18.       int[] aux = new int[n];
  20.       while (m / exp > 0) { // Go through all digits from LSB to MSB
  21.         int[] count = new int[R];
  23.         for (int i = 0; i < n; i++) {
  24.           count[(nums[i] / exp) % 10]++;
  25.         }
  27.         for (int i = 1; i < R; i++) {
  28.           count[i] += count[i - 1];
  29.         }
  31.         for (int i = n - 1; i >= 0; i--) {
  32.           aux[--count[(nums[i] / exp) % 10]] = nums[i];
  33.         }
  35.         for (int i = 0; i < n; i++) {
  36.             nums[i] = aux[i];
  37.         }
  39.         exp *= 10;
  40.       }
  42.       int max = 0;
  43.       for (int i = 1; i < aux.length; i++) {
  44.         max = Math.max(max, aux[i] - aux[i - 1]);
  45.       }
  47.       return max;
  48.   }
  49. }